// hdu5745
// 题意：
// 给定一个串s(长度<=10^5), 串t(长度<=5000)，你可以对串t选择任意个不相邻的
// 位置和这些位置的前一个字符交换，问对于串s的每个位置是不是可以往后匹配上
// 串t（每次串t可以不变换，也可以经过一次变换，每个位置变换独立）。
//
// 题解：
// 首先可以想到一个二维的dp，
// f[i][j][k]表示s的前i个位置匹配t的前j个位置当前字符状态是k是否可以成功，
// k=0, 1, 2 分别表示往前交换，不交换或者往后交换。
//
// f[i][j][0] = f[i-1][j-1][2] && s[i] == t[j-1]
// f[i][j][1] = (f[i-1][j-1][0] || f[i-1][j-1][1]) && s[i] == t[j]
// f[i][j][2] = (f[i-1][j-1][0] || f[i-1][j-1][1]) && s[i] == t[j+1]
//
// 注意到这个dp状态都是bool值，所以我们可以将j这一维度用bitset储存，然后
// 对于i进行滚存，每次按照上面的方程将j这维整体进行转移，
// 复杂度是O(n*m/w)，w是机器字长。
//
// run: time -p $exec < input
// opt: 0
// flag: -g
#include <iostream>
#include <bitset>

int const maxm = 5007;
std::bitset<maxm> f[2][3];
std::bitset<maxm> d[26], l[26], r[26];
std::string ans;
std::string s, t;
int n, m;

void work()
{
	for (int i = 0; i < 26; i++) d[i].reset();
	for (int i = 0; i < m; i++) d[t[i] - 'a'].set(i);
	for (int i = 0; i < 26; i++) {
		l[i] = d[i] << 1;
		r[i] = d[i] >> 1;
	}

	ans.clear();
	ans.resize(n, '0');
	int now = 0, prev = 1;
	for (int i = 0; i < 3; i++) f[now][i].set();
	for (int i = 0; i < n; i++) {
		now ^= 1; prev ^= 1;
		f[now][0] = f[prev][2] << 1;
		f[now][1] = (f[prev][0] | f[prev][1]) << 1;
		f[now][1][0] = f[now][0][0] = 1;
		f[now][2] = f[now][1];
		int del = s[i] - 'a';
		f[now][0] &= l[del];
		f[now][1] &= d[del];
		f[now][2] &= r[del];
		if (i >= m - 1 && (f[now][0][m - 1] || f[now][1][m - 1]))
			ans[i - m + 1] = '1';
	}
	std::cout << ans << "\n";
}

int main()
{
	std::ios_base::sync_with_stdio(false);
	int T; std::cin >> T;
	while (T--) {
		std::cin >> n >> m >> s >> t;
		work();
	}
}

